home *** CD-ROM | disk | FTP | other *** search
/ Java Programmer's Toolkit / Java Programmer's Toolkit.iso / applets / collectn / hashedma.jav < prev    next >
Encoding:
Text File  |  1995-12-14  |  14.0 KB  |  550 lines
  1. /*
  2.   File: HashedMap.java
  3.  
  4.   Originally written by Doug Lea and released into the public domain. 
  5.   Thanks for the assistance and support of Sun Microsystems Labs, Agorics 
  6.   Inc, Loral, and everyone contributing, testing, and using this code.
  7.  
  8.   History:
  9.   Date     Who                What
  10.   24Sep95  dl@cs.oswego.edu   Create from collections.java  working file
  11.   13Oct95  dl                 Changed protection statuses
  12.   21Oct95  dl                 fixed error in removeAt
  13.  
  14. */
  15.   
  16. package collections;
  17.  
  18. import java.util.Enumeration;
  19. import java.util.NoSuchElementException;
  20.  
  21. /**
  22.  *
  23.  * Hash table implementation of Map
  24.  * @author Doug Lea
  25.  * @version 0.94
  26.  *
  27.  * <P> For an introduction to this package see <A HREF="index.html"> Overview </A>.
  28. **/
  29.  
  30.  
  31. public class HashedMap extends    UpdatableMapImpl 
  32.                        implements UpdatableMap, HashTableParams {
  33.  
  34. // instance variables 
  35.  
  36. /**
  37.  * The table. Each entry is a list. Null if no table allocated
  38. **/
  39.   protected LLPair table_[];
  40.  
  41. /**
  42.  * The threshold load factor
  43. **/
  44.  
  45.   protected float loadFactor_;
  46.  
  47.  
  48. // constructors
  49.  
  50. /** 
  51.  * Make a new empty map.
  52. **/
  53.  
  54.   public HashedMap() { this(null, defaultLoadFactor); }
  55.  
  56. /** 
  57.  * Make a new empty map to use given element screener.
  58. **/
  59.  
  60.   public HashedMap(Predicate screener) { this(screener, defaultLoadFactor); }
  61.  
  62. /**
  63.  * Special version of constructor needed by clone()
  64. **/
  65.  
  66.   protected HashedMap(Predicate s, float f) { 
  67.     super(s); table_ = null; loadFactor_ = f;
  68.   }
  69.  
  70. /**
  71.  * Make an independent copy of the table. Elements themselves are not cloned.
  72. **/
  73.  
  74.   protected Object clone() throws CloneNotSupportedException { 
  75.     HashedMap c =  new HashedMap(screener_, loadFactor_);
  76.     if (count_ != 0) {
  77.       int cap = 2 * (int)((count_ / loadFactor_)) + 1;
  78.       if (cap < defaultInitialBuckets) cap = defaultInitialBuckets;
  79.       c.buckets(cap);
  80.       for (int i = 0; i < table_.length; ++i) {
  81.         for (LLPair p = table_[i]; p != null; p = (LLPair)(p.next())) 
  82.           c.putAt(p.key(), p.element());
  83.       }
  84.     }
  85.     return c;
  86.   }
  87.  
  88.  
  89. // HashTableParams methods
  90.  
  91. /**
  92.  * Implements collections.HashTableParams.buckets.
  93.  * Time complexity: O(1).
  94.  * @see collections.HashTableParams#buckets.
  95. **/
  96.  
  97.   public synchronized int buckets() { 
  98.     return (table_ == null)? 0 : table_.length; 
  99.   }
  100.  
  101. /**
  102.  * Implements collections.HashTableParams.buckets.
  103.  * Time complexity: O(n).
  104.  * @see collections.HashTableParams#buckets.
  105. **/
  106.  
  107.   public synchronized void buckets(int newCap) 
  108.   throws IllegalArgumentException {
  109.     if (newCap == buckets()) 
  110.       return;
  111.     else if (newCap >= 1) 
  112.       resize(newCap);
  113.     else 
  114.       throw new IllegalArgumentException("Impossible Hash table size:" + newCap);
  115.  
  116.   }
  117.  
  118. /**
  119.  * Implements collections.HashTableParams.thresholdLoadfactor
  120.  * Time complexity: O(1).
  121.  * @see collections.HashTableParams#thresholdLoadfactor
  122. **/
  123.  
  124.   public synchronized float thresholdLoadFactor() { 
  125.     return loadFactor_;
  126.   }
  127.  
  128. /**
  129.  * Implements collections.HashTableParams.thresholdLoadfactor
  130.  * Time complexity: O(n).
  131.  * @see collections.HashTableParams#thresholdLoadfactor
  132. **/
  133.  
  134.   public synchronized void thresholdLoadFactor(float desired)
  135.   throws IllegalArgumentException {
  136.     if (desired > 0.0) {
  137.       loadFactor_ = desired;
  138.       checkLoadFactor();
  139.     }
  140.     else
  141.       throw new IllegalArgumentException("Impossible Hash table load factor:" + desired);
  142.   }
  143.  
  144.  
  145.  
  146.  
  147. // Collection methods
  148.  
  149. /**
  150.  * Implements collections.Collection.includes.
  151.  * Time complexity: O(1) average; O(n) worst.
  152.  * @see collections.Collection#includes
  153. **/
  154.   public synchronized boolean includes(Object element) {
  155.     if (element == null || count_ == 0) return false;
  156.     for (int i = 0; i < table_.length; ++i) {
  157.       LLPair hd =  table_[i];
  158.       if (hd != null && hd.find(element) != null) return true;
  159.     }
  160.     return false;
  161.   }
  162.  
  163. /**
  164.  * Implements collections.Collection.occurrencesOf.
  165.  * Time complexity: O(n).
  166.  * @see collections.Collection#occurrencesOf
  167. **/
  168.   public synchronized int occurrencesOf(Object element) {
  169.     if (element == null || count_ == 0) return 0;
  170.     int c = 0;
  171.     for (int i = 0; i < table_.length; ++i) {
  172.       LLPair hd = table_[i];
  173.       if (hd != null) c += hd.count(element);
  174.     }
  175.     return c;
  176.   }
  177.  
  178. /**
  179.  * Implements collections.Collection.elements.
  180.  * Time complexity: O(1).
  181.  * @see collections.Collection#elements
  182. **/
  183.   public synchronized CollectionEnumeration elements() { 
  184.     return new HTPairEnumeration(this, table_, false); 
  185.   }
  186.  
  187.  
  188. // Map methods
  189.  
  190.  
  191. /**
  192.  * Implements collections.Map.includesKey.
  193.  * Time complexity: O(1) average; O(n) worst.
  194.  * @see collections.Map#includesKey
  195. **/
  196.   public synchronized boolean  includesKey(Object key) {
  197.     if (key == null || count_ == 0) return false;
  198.     LLPair p = table_[hashOf(key)];
  199.     if (p != null) return p.findKey(key) != null;
  200.     else return false;
  201.   }
  202.   
  203. /**
  204.  * Implements collections.Map.includesAt
  205.  * Time complexity: O(1) average; O(n) worst.
  206.  * @see collections.Map#includesAt
  207. **/
  208.   public synchronized boolean includesAt(Object key, Object element) {
  209.     if (key == null || element == null || count_ == 0) return false;
  210.     LLPair p = table_[hashOf(key)];
  211.     if (p != null) return p.find(key, element) != null;
  212.     else return false;
  213.   }
  214.  
  215. /**
  216.  * Implements collections.Map.keys.
  217.  * Time complexity: O(1).
  218.  * @see collections.Map#keys
  219. **/
  220.   public synchronized CollectionEnumeration keys() { 
  221.     return new HTPairEnumeration(this, table_, true); 
  222.   }
  223.  
  224. /**
  225.  * Implements collections.Map.at.
  226.  * Time complexity: O(1) average; O(n) worst.
  227.  * @see collections.Map#at
  228. **/
  229.   public synchronized Object at(Object key) 
  230.   throws  NoSuchElementException {
  231.     checkKey(key);
  232.     if (count_ != 0) {
  233.       LLPair p = table_[hashOf(key)];
  234.       if (p != null) {
  235.         LLPair c =  p.findKey(key);
  236.         if (c != null) return c.element();
  237.       }
  238.     }
  239.     throw new NoSuchElementException("no Key matching argument " + key);
  240.   }
  241.  
  242. /**
  243.  * Implements collections.Map.aKeyOf.
  244.  * Time complexity: O(n).
  245.  * @see collections.Map#aKeyOf
  246. **/
  247.   public synchronized Object aKeyOf(Object element) {
  248.     if (element == null || count_ == 0) return null;
  249.     for (int i = 0; i < table_.length; ++i) {
  250.       LLPair hd =  table_[i];
  251.       if (hd != null) {
  252.         LLPair p = ((LLPair)(hd.find(element)));
  253.         if (p != null) return p.key();
  254.       }
  255.     }
  256.     return null;
  257.   }
  258.   
  259.  
  260. // UpdatableCollection methods
  261.  
  262. /**
  263.  * Implements collections.UpdatableCollection.clear.
  264.  * Time complexity: O(1).
  265.  * @see collections.UpdatableCollection#clear
  266. **/
  267.   public synchronized void clear() { 
  268.     setCount(0);
  269.     table_ = null;
  270.   }
  271.  
  272. /**
  273.  * Implements collections.UpdatableCollection.exclude.
  274.  * Time complexity: O(n).
  275.  * @see collections.UpdatableCollection#exclude
  276. **/
  277.   public synchronized void exclude(Object element) {
  278.     remove_(element, true);
  279.   }
  280.  
  281.  
  282. /**
  283.  * Implements collections.UpdatableCollection.removeOneOf.
  284.  * Time complexity: O(n).
  285.  * @see collections.UpdatableCollection#removeOneOf
  286. **/
  287.   public synchronized void removeOneOf(Object element) {
  288.     remove_(element, false);
  289.   }
  290.  
  291.  
  292. /**
  293.  * Implements collections.UpdatableCollection.replaceOneOf.
  294.  * Time complexity: O(n).
  295.  * @see collections.UpdatableCollection#replaceOneOf
  296. **/
  297.   public synchronized void replaceOneOf(Object oldElement, Object newElement) 
  298.   throws IllegalElementException {
  299.     replace_(oldElement, newElement, false);
  300.   }
  301.  
  302. /**
  303.  * Implements collections.UpdatableCollection.replaceAllOf.
  304.  * Time complexity: O(n).
  305.  * @see collections.UpdatableCollection#replaceAllOf
  306. **/
  307.   public synchronized void replaceAllOf(Object oldElement, Object newElement) 
  308.   throws IllegalElementException {
  309.     replace_(oldElement, newElement, true);
  310.   }
  311.  
  312. /**
  313.  * Implements collections.UpdatableCollection.take.
  314.  * Time complexity: O(number of buckets).
  315.  * @see collections.UpdatableCollection#take
  316. **/
  317.   public synchronized Object take() 
  318.   throws NoSuchElementException {
  319.     if (count_ != 0) {
  320.       for (int i = 0; i < table_.length; ++i) {
  321.         if (table_[i] != null) {
  322.           decCount();
  323.           Object v = table_[i].element();
  324.           table_[i] = (LLPair)(table_[i].next());
  325.           return v;
  326.         }
  327.       }
  328.     }
  329.     checkIndex(0);
  330.     return null; // not reached
  331.   }
  332.  
  333. // UpdatableMap methods
  334.  
  335.  
  336. /**
  337.  * Implements collections.UpdatableMap.putAt.
  338.  * Time complexity: O(1) average; O(n) worst.
  339.  * @see collections.UpdatableMap#putAt
  340. **/
  341.   public synchronized void  putAt(Object key, Object element) {
  342.     checkKey(key);
  343.     checkElement(element);
  344.     if (table_ == null) resize(defaultInitialBuckets);
  345.     int h = hashOf(key);
  346.     LLPair hd = table_[h];
  347.     if (hd == null) {
  348.       table_[h] = new LLPair(key, element, hd);
  349.       incCount();
  350.       return;
  351.     }
  352.     else {
  353.       LLPair p = hd.findKey(key);
  354.       if (p != null) {
  355.         if (!p.element().equals(element)) {
  356.           p.element(element);
  357.           incVersion();
  358.         }
  359.       }
  360.       else {
  361.         table_[h] = new LLPair(key, element, hd);
  362.         incCount();
  363.         checkLoadFactor(); // we only check load factor on add to nonempty bin
  364.       }
  365.     }
  366.   }
  367.  
  368.  
  369. /**
  370.  * Implements collections.UpdatableMap.removeAt.
  371.  * Time complexity: O(1) average; O(n) worst.
  372.  * @see collections.UpdatableMap#removeAt
  373. **/
  374.   public synchronized void removeAt(Object key) {
  375.     if (key == null || count_ == 0) return;
  376.     int h = hashOf(key);
  377.     LLPair hd = table_[h];
  378.     LLPair p = hd;
  379.     LLPair trail = p;
  380.     while (p != null) {
  381.       LLPair n = (LLPair)(p.next());
  382.       if (p.key().equals(key)) {
  383.         decCount();
  384.         if (p == hd) table_[h] = n;
  385.         else trail.unlinkNext();
  386.         return;
  387.       }
  388.       else {
  389.         trail = p;
  390.         p = n;
  391.       }
  392.     }
  393.   }
  394.  
  395. /**
  396.  * Implements collections.UpdatableMap.replaceElement.
  397.  * Time complexity: O(1) average; O(n) worst.
  398.  * @see collections.UpdatableMap#replaceElement
  399. **/
  400.   public synchronized void replaceElement(Object key, Object oldElement, 
  401.                                           Object newElement)  
  402.     throws IllegalElementException { 
  403.     if (key == null || oldElement == null || count_ == 0) return;
  404.     LLPair p = table_[hashOf(key)];
  405.     if (p != null) {
  406.       LLPair c = p.find(key, oldElement);
  407.       if (c != null) {
  408.         checkElement(newElement);
  409.         c.element(newElement);
  410.         incVersion();
  411.       }
  412.     }
  413.   }
  414.  
  415. // Helper methods
  416.  
  417. /**
  418.  * Check to see if we are past load factor threshold. If so, resize
  419.  * so that we are at half of the desired threshold.
  420.  * Also while at it, check to see if we are empty so can just
  421.  * unlink table.
  422. **/
  423.   protected void checkLoadFactor() {
  424.     if (table_ == null) {
  425.       if (count_ != 0) resize(defaultInitialBuckets);
  426.     }
  427.     else {
  428.       float fc = (float)(count_);
  429.       float ft = table_.length;
  430.       if (fc / ft > loadFactor_) {
  431.         int newCap = 2 * (int)(fc / loadFactor_) + 1;
  432.         resize(newCap);
  433.       }
  434.     }
  435.   }
  436.  
  437. /**
  438.  * Mask off and remainder the hashCode for element
  439.  * so it can be used as table index
  440. **/
  441.  
  442.   protected final int hashOf(Object element) {
  443.     return (element.hashCode() & 0x7FFFFFFF) % table_.length;
  444.   }
  445.  
  446.  
  447.   protected void resize(int newCap) {
  448.     LLPair newtab[] = new LLPair[newCap];
  449.     
  450.     if (table_ != null) {
  451.       for (int i = 0; i < table_.length; ++i) {
  452.         LLPair p = table_[i];
  453.         while (p != null) {
  454.           LLPair n = (LLPair)(p.next());
  455.           int h =  (p.key().hashCode() & 0x7FFFFFFF) % newCap;
  456.           p.next(newtab[h]);
  457.           newtab[h] = p;
  458.           p = n;
  459.         }
  460.       }
  461.     }
  462.     table_ = newtab;
  463.     incVersion();
  464.   }
  465.  
  466. // helpers
  467.  
  468.   private void remove_(Object element, boolean allOccurrences) {
  469.     if (element == null || count_ == 0) return;
  470.     for (int h = 0; h < table_.length; ++h) {
  471.       LLCell hd = table_[h];
  472.       LLCell p = hd;
  473.       LLCell trail = p;
  474.       while (p != null) {
  475.         LLPair n = (LLPair)(p.next());
  476.         if (p.element().equals(element)) {
  477.           decCount();
  478.           if (p == table_[h]) { table_[h] = n; trail = n; }
  479.           else trail.next(n);
  480.           if (!allOccurrences) return;
  481.           else p = n;
  482.         }
  483.         else {
  484.           trail = p;
  485.           p = n;
  486.         }
  487.       }
  488.     }
  489.   }
  490.  
  491.   private void replace_(Object oldElement, Object newElement, boolean allOccurrences) 
  492.     throws IllegalElementException {
  493.     if (count_ == 0 || oldElement == null || oldElement.equals(newElement))
  494.       return;
  495.  
  496.     for (int h = 0; h < table_.length; ++h) {
  497.       LLCell hd = table_[h];
  498.       LLCell p = hd;
  499.       LLCell trail = p;
  500.       while (p != null) {
  501.         LLPair n = (LLPair)(p.next());
  502.         if (p.element().equals(oldElement)) {
  503.           checkElement(newElement);
  504.           incVersion();
  505.           p.element(newElement);
  506.           if (!allOccurrences) return;
  507.         }
  508.         trail = p;
  509.         p = n;
  510.       }
  511.     }
  512.   }
  513.  
  514. // ImplementationCheckable methods
  515.  
  516. /**
  517.  * Implements collections.ImplementationCheckable.checkImplementation.
  518.  * @see collections.ImplementationCheckable#checkImplementation
  519. **/
  520.   public synchronized void checkImplementation() 
  521.   throws ImplementationError {
  522.     super.checkImplementation();
  523.  
  524.     assert(!(table_ == null && count_ != 0));
  525.     assert((table_ == null || table_.length > 0));
  526.     assert(loadFactor_ > 0.0f);
  527.  
  528.     if (table_ == null) return;
  529.     int c = 0;
  530.     for (int i = 0; i < table_.length; ++i) {
  531.       for (LLPair p = table_[i]; p != null; p = (LLPair)(p.next())) {
  532.         ++c;
  533.         assert(canInclude(p.element()));
  534.         assert(canIncludeKey(p.key()));
  535.         assert(includesKey(p.key()));
  536.         assert(includes(p.element()));
  537.         assert(occurrencesOf(p.element()) >= 1);
  538.         assert(includesAt(p.key(), p.element()));
  539.         assert(hashOf(p.key()) == i);
  540.       }
  541.     }
  542.     assert(c == count_);
  543.    
  544.  
  545.   }
  546.  
  547.    
  548. }
  549.  
  550.